public class test1 {
    class Solution {
        List<String> res;
        String[] strs;
        StringBuilder sb;
        public List<String> letterCombinations(String digits) {
            sb = new StringBuilder();
            res = new ArrayList<>();
            if(digits==null || digits.length()==0){
                return res;
            }
            strs = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
            backTracking(digits,0);
            return res;
        }
        private void backTracking(String digits,int start){
            if(digits.length()==sb.length()){
                res.add(sb.toString());
                return;
            }
            String str = strs[digits.charAt(start)-'0'];
            for(int i = 0;i<str.length();i++){
                sb.append(str.charAt(i));
                backTracking(digits,start+1);
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }
}
